package dataStructure.sort.bubbleSort;

/**
 * @author lhn
 * @date 2024-08-29 15:18
 */

public class BubbleSort_optimize {
    //冒泡排序的时间复杂度：O(n^2)
    public static void main(String[] args) {
        int[] arr = {3, 9, -1, 10, 20};
        System.out.println("排序前：");
        print(arr);
        sort(arr);
        System.out.println("排序后：");
        print(arr);

        int[] arrTest = new int[80000];
        for (int i = 0; i < arrTest.length; i++) {
            arrTest[i] = (int) (Math.random() * 80000);
        }
    }

    public static int[] sort(int[] arr){
        boolean flag = false;   //一趟排序中是否存在交换的情况
        for (int i = 0; i < arr.length - i; i++) {
            // 外层循环控制比较轮数
            System.out.println("=============第" + (i + 1) + "轮比较：=============");
            for (int j = 0; j < arr.length - 1 - i; j++) {
                System.out.println("比较：" + arr[j] + "和" + arr[j + 1]);
                if (arr[j] > arr[j + 1]) {
                    flag = true;    //存在交换的情况
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
                print(arr);
            }
            if (!flag){
                // 没有发生交换，说明已经排好序，可以退出循环
                break;
            } else {
                flag = false;
            }
        }
        return arr;
    }

    public static void print(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}
